/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/implement-strstr
   @Language: C++
   @Datetime: 19-05-31 10:11
   */

// Method 1, KMP
class Solution {
	void getnext(string &str, vector<int> &next){
		for(int i=0, j=-1; i<str.length();){
			if(j==-1 || str[i]==str[j]){
				++i, ++j;
				next[i]=(str[i]==str[j]?next[j]:j);
			}
			else j=next[j];
		}
	}
public:
	int strStr(string &haystack, string &needle) {
		int lh=haystack.length(), ln=needle.length();
		vector<int> next(ln+1,-1);
		getnext(needle,next);
		int i=0, j=0;
		while(i<lh && j<ln){
			if(j==-1 || haystack[i]==needle[j]) ++i, ++j;
			else j=next[j];
		}
		return j==ln?i-j:-1;
	}
};

// Method 2, std
class Solution {
public:
	int strStr(string &haystack, string &needle) {
		return haystack.find(needle);
	}
};
